package com.aitao.beans;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BitMap {

    private int[] bitArray;

    private static final int MASK = 0x1F; // 2^5-1

    //int 占用4个字节,所以size / 32 = size >> 5
    public BitMap(int size) {
        bitArray = new int[(int) (((size - 1) >> 5) + 1)];
        Arrays.fill(bitArray, 0);
    }

    /**
     * 寻址:设置比较位为1z
     * (1)确定数组index：index = 119 / 32 = Math.floor(3.7);
     * (2)确定比特位index: index = 119 % 32 = 23,左移 1 << 23
     * (3)设置比特位为1：将1左移bitIndex位，然后与原来的值进行或运算。
     */
    public void set1(int num) {
        //确定数组 index
        int arrayIndex = num >> 5; // num / 32
        //确定比特位 index
        int bitIndex = num & 31;// num % 32
        //设置比特位为1
        bitArray[arrayIndex] |= 1 << bitIndex;
        //bitArray[num >> 5] |= (1 << (num & 3));
        System.out.println(get32BitBinString(bitArray[arrayIndex]));
    }

    /**
     * 寻址:设置比较位为0
     * (1)确定数组index：index = 119 / 32 = Math.floor(3.7);
     * (2)确定比特位index: index = 119 % 32 = 23,左移 1 << 23
     * (3)设置比特位为0：将1左移bitIndex位，并进行非运算，然后与原来的值进行与运算。
     */
    public void set0(int num) {
        //确定数组 index
        int arrayIndex = num >> 5;// num / 32
        //确定比特位 index
        int bitIndex = num & 31;// num % 32
        //设置比特位为0
        bitArray[arrayIndex] &= ~(1 << bitIndex);
    }

    /**
     * 寻址:判断指定比特位是否存在元素
     * (1)确定数组index：index = 119 / 32 = Math.floor(3.7);
     * (2)确定比特位index: index = 119 % 32 = 23,左移 1 << 23
     * (3)设置比特位为0：将1左移bitIndex位，然后与原来的值进行与运算。只要与运算结果中有1，即表示元素存在。
     */
    public boolean isExist(int num) {
        //确定数组 index
        int arrayIndex = num >> 5;
        //确定比特位 index
        int bitIndex = num & 31;
        //判断是否存在
        return (bitArray[arrayIndex] & ((1 << bitIndex))) != 0;
    }

    /**
     * 将整型数字转换为二进制字符串，一共32位，不舍弃前面的0
     *
     * @param number 整型数字
     * @return 二进制字符串
     */
    private static String get32BitBinString(int number) {
        StringBuilder sBuilder = new StringBuilder();
        for (int i = 0; i < 32; i++) {
            sBuilder.append(number & 1);
            number = number >>> 1;
        }
        return sBuilder.reverse().toString();
    }

    public static void bitMapSort(int[] array) {
        int size = Arrays.stream(array).max().getAsInt();
        List<Integer> list = new ArrayList<>();
        long[] bits = new long[((size - 1) >> 6) + 1];//(100-1)/64+1=4,开辟了4*4大小的数组来存放数据
        System.out.println(bits.length);
        for (int k : array) {
            bits[k >> 6] |= 1L << (k & 63); //设置1
        }
        for (int i = 0; i < bits.length; i++) {//扫描一次
            for (int j = 0; j < 64; j++) {
                if ((bits[i] & (1L << j)) != 0) {//判断元素是否存在
                    list.add((i << 6) + j);
                }
            }
        }
        System.out.println(list);
    }
}

